package dfs

// https://leetcode-cn.com/problems/combination-sum/
// 动态规划
// dfs

type retTwoArr struct {
	RetArr [][]int
}

func dfsForCombination(remain int, candidateMap map[int]string, currentNumArr []int, ret *retTwoArr) {
	if remain < 0 {
		return
	}
	for currentCandidate := range candidateMap {
		tempArr := make([]int, len(currentNumArr))
		copy(tempArr, currentNumArr)
		if remain-currentCandidate < 0 {
			continue
		} else if remain-currentCandidate == 0 {
			tempArr = append(tempArr, currentCandidate)
			ret.RetArr = append(ret.RetArr, tempArr)
		} else {
			tempArr = append(tempArr, currentCandidate)
			dfsForCombination(remain-currentCandidate, candidateMap, tempArr, ret)
		}
	}
}

func CombinationSum(candidates []int, target int) [][]int {
	retArr := make([][]int, 0)
	retStru := new(retTwoArr)
	retStru.RetArr = retArr

	candidateMap := make(map[int]string)

	for _, currentCandidate := range candidates {
		candidateMap[currentCandidate] = "1"
	}

	dfsForCombination(target, candidateMap, []int{}, retStru)
	return retStru.RetArr
}
